package datastruct.sortedset;


import java.util.Random;
import java.util.Stack;

// 实现参考：https://www.cnblogs.com/bigsai/p/14193225.html
public class SkipList<T> {
    private SkipNode<T> head;
    private int highLevel;
    private Random random;

    public static final int MAX_LEVEL = 32;

    public SkipList() {
        random = new Random();
        head = new SkipNode("", null);
        highLevel = 0;
    }

    public SkipNode<T> search(String key) {
        SkipNode<T> temp = head;
        // 从 head 开始，从左往右，从上往下找
        while (temp != null) {
            if (temp.key.equals(key)) {
                return temp;
            } else if (temp.right == null) {
                // 右边已经没了，只能往下
                temp = temp.down;
            } else if (temp.right.key.compareTo(key) > 0) {
                // 右边比要查找的 key 大，那么 key 应该在当前节点和右边节点组成的节点范围内，那么往下
                temp = temp.down;
            } else {
                // 右边小于 key，那么继续向右
                temp = temp.right;
            }
        }
        return null;
    }

    public void delete(String key) {
        SkipNode<T> temp = head;
        while (temp != null) {
            if (temp.right == null) {
                // 右边没了，只能往下
                temp = temp.down;
            } else if (temp.right.key.equals(key)) {
                // 先删除右侧节点
                temp.right = temp.right.right;
                // 让后继续往下
                temp = temp.down;
            } else if (temp.right.key.compareTo(key) < 0) {
                // 继续往右
                temp = temp.right;
            } else {
                // 右边所有节点比 key 大了，只能往下
                temp = temp.down;
            }
        }
    }

    public void add(SkipNode<T> node) {
        // 先判断这个节点是否已经存在，如果存在，那么直接更新 value
        SkipNode<T> n = search(node.key);
        if (n != null) {
            n.value = node.value;
            return;
        }
        // 用来存查找过程中遍历的 节点
        Stack<SkipNode<T>> st = new Stack<>();
        SkipNode<T> temp = head;
        while (temp != null) {
            if (temp.right == null) {
                // 右边没了，只能往下
                st.push(temp);
                temp = temp.down;
            } else if (temp.right.key.compareTo(node.key) < 0) {
                temp = temp.right;
            } else {
                // 右边比 node.key 大，只能往下，同时，这个位置就是一个插入点, 先把插入点放入栈中，之后，从下往上依次加入节点
                st.push(temp);
                temp = temp.down;
            }
        }

        // 当前层数
        int level = 1;
        SkipNode<T> downNode = null;
        SkipNode<T> nd;
        while (!st.isEmpty()) {
            // 第一次进入循环，是在最底层，而最底层是必须添加
            nd = st.pop();
            SkipNode<T> newNode = new SkipNode<>(node.key, node.value);
            newNode.down = downNode;
            if (nd.right == null) {
                nd.right = newNode;
            } else {
                newNode.right = nd.right;
                nd.right = newNode;
            }
            downNode = newNode;


            // 考虑是否向上添加
            if (level > MAX_LEVEL) {
                break;
            }

            // 通过概率来判断是否要往上添加
            int p = random.nextInt(101);
            if (p > 50) {
                break;
            }
            level++;
            // 如果新增的高度比当前的最大高度还高，但是小于 MAX_LEVEL, 那么需要新增 head
            if (level > highLevel) {
                highLevel = level;
                SkipNode<T> newHead = new SkipNode<T>("", null);
                newHead.down = head;
                head = newHead;
                st.push(head);

            }
        }
    }

    public void printSkipList() {
        // tempHead 指向最上层 head 节点
        SkipNode<T> tempHead = head;
        SkipNode<T> bottomHead = head;
        // 让 bottomHead 指向最底层 head 节点
        while (bottomHead.down != null) {
            bottomHead = bottomHead.down;
        }

        SkipNode<T> p, b;

        while (tempHead != null) {
            p = tempHead.right;
            b = bottomHead.right;
            // 左对齐
            System.out.printf("%-8s", "head->");
            while (p != null && b != null) {
                if (p.key == b.key) {
                    System.out.printf("%-5s", p.key + "->");
                    p = p.right;
                    b = b.right;
                } else {
                    b = b.right;
                    System.out.printf("%-5s", "");
                }
            }
            // 上面 while 循环结束，表示一层已经打印完，需要挪到下一层
            tempHead = tempHead.down;
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SkipList<Integer> skipList = new SkipList<>();
        char a = 'A';
        for (int i=0;i<20;i++) {
            skipList.add(new SkipNode<Integer>(String.valueOf((char) (a+i)), 666));
        }
        System.out.println("删除前");
        skipList.printSkipList();
        skipList.delete("B");
        skipList.delete("D");
        System.out.println("删除后");
        skipList.printSkipList();
    }
}